#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    public:
    //my ans
    int ans1(vector<int>& height){
        int length = height.size();
        int max_val = 0;
        for(int i = 0; i != length; i++){
            max_val = max(height[i], max_val);
        }
        vector<int> water(length, max_val);
        for(int i = 0; i != length; i++){
            water[i] = water[i] - height[i];
        }
        while(true){
            int p1 = 0, p2 = length-1;
            while(water[p1] != 0){
                water[p1]--;
                p1++;
            }
            while(water[p2] != 0){
                water[p2]--;
                p2--;
            }
            if(water[0] == 0 && water[length-1] == 0){
                break;
            }
        }
        int total_water = 0;
        for(int i = 0; i != length; i++){
            total_water = total_water + water[i];
        }

        return total_water;
    }

    //动态规划
    int ans2(vector<int>& height){
        int length = height.size();
        vector<int> left_water(length, 0);
        vector<int> right_water(length, 0);
        int left_max = 0, right_max = 0;
        for(int i = 0; i != length; i++){
            if(height[i] > left_max){
                left_max = height[i];
            }
            left_water[i] = left_max;
            if(height[length-i-1] > right_max){
                right_max = height[length-i-1];
            }
            right_water[length-i-1] = right_max;
        }
        int total_water = 0;
        for(int i = 0; i != length; i++){
            total_water = total_water + min(left_water[i], right_water[i]) - height[i];
        }

        return total_water;
    }

    //双指针
    int ans3(vector<int>& height){
        int length = height.size();
        int p1 = 0, p2 = length-1;
        int total_water = 0;
        int left_max = 0, right_max = 0;
        while(p1 < p2){
            if(height[p1] > left_max){
                left_max = height[p1];
            }
            if(height[p2] > right_max){
                right_max = height[p2];
            }
            if(height[p1] >= height[p2]){
                total_water = total_water + right_max - height[p2];
                p2--;
            }else{
                total_water = total_water + left_max - height[p1];
                p1++;
            }
        }

        return total_water;
    }

};

void test1(){
    Solution s;
    vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    // int water = s.ans1(height);
    // int water = s.ans2(height);
    int water = s.ans3(height);
    cout << water << endl;
}

void test2(){
    Solution s;
    vector<int> height = {4,2,0,3,2,5};
    // int water = s.ans1(height);
    // int water = s.ans2(height);
    int water = s.ans3(height);
    cout << water << endl;
}


int main(void){
    test1();
    test2();

    return 0;
}